package 二分查找.easy;

import com.sun.javafx.collections.MappingChange;

import java.util.*;

/**
 * 1. 问题描述
 *       给你一个大小为m* n的矩阵mat，矩阵由若干军人和平民组成，分别用 1 和 0 表示。
 *       请你返回矩阵中战斗力最弱的k行的索引，按从最弱到最强排序。
 *       如果第i行的军人数量少于第j行，或者两行军人数量相同但 i 小于 j，那么我们认为第 i 行的战斗力比第 j 行弱。
 *       军人 总是 排在一行中的靠前位置，也就是说 1 总是出现在 0 之前。
 *
 * 2. 算法分析
 *      分析题意：
 *          对于此题而言，所谓的强弱有两种方式比较
 *              1. 如果第i行的军人的数量少于第j行军人的数量，则称第i行比第j行弱
 *              2. 如果第i行和第j行的军人数量相同，并且第i行出现在第j行之前，此时也称第i行比第j行弱
 *              总而言之：
 *                  当两行的军人数量相同，比较行号即可
 *                  不同直接比较军人数量即可
 *
 *          当我们有n行，每行有m个人(包括军人和平民组成)，我们的目的是找出最弱的k行
 *
 *      算法分析：
 *          给一个具体的例子：        行号      行军人数量
 *              [                  row      stronger
 *                  [1,1,0,0,0],    0           2
 *                  [1,1,1,1,0],    1           4
 *                  [1,0,0,0,0],    2           1
 *                  [1,1,0,0,0],    3           2
 *                  [1,1,1,1,1]     4           5
 *              ]
 *
 *          count = [2,4,1,2,5]   count[i]表示第i行有count[i]个军人数量
 *          我们现在从count中选出最弱的k行
 *
 *          k = 1，即找出数组中的最小值  2
 *              1. 最小值唯一，则为最弱
 *              2. 最小值不唯一，返回索引最小的一个
 *
 *          k = 2，我们需要找到数组中的两个最弱行 0 2 滑动窗口
 *
 * 3. 代码实现
 *
 *
 */
@SuppressWarnings("all")
public class 矩阵中战斗力最弱的K行 {
    public static void main(String[] args) {
        int[][] mat = {
                {1,1,0,0,0},
                {1,1,1,1,0},
                {1,0,0,0,0},
                {1,1,0,0,0},
                {1,1,1,1,1}
        };
        int k = 3;
        int[] ans = kWeakestRows(mat, k);
        // 测试sortedMap
        SortedMap<Integer,Integer> map =  new TreeMap<>();
        map.put(0,3);
        map.put(1,2);
        map.put(2,1);
        for (Integer integer : map.keySet()) {
            System.out.println(map.get(integer));
        }
    }

    /**
     * 首先我们第一想法就是将考虑这样的数据结构(行号，行军人数)，然后对这样的数据结构(行军人数)进行排序
     *         返回前k个()中的行号即可
     *         但是Java中并没有直接的数据结构(此题使用Python会非常简单，因为有直接的数据结构可以调用，几行代码搞定)
     *         所以我们需要考虑使用Java已有的数据结构来考虑此题，我们知道Java中内置的Arrays类中的sorted函数可以实现
     *         对数组进行排序，所以此题我们采用数组来解决此题，但是此时我们面临一个问题这个数组中的元素是什么呢?我们既
     *         要存放每行士兵的个数，有需要记住当前行行号，如何解决呢?
     *         解决方式：
     *             由于题目要求2 <= n,m <= 100,所以矩阵最大也就是100*100的，所以此时我们采用如下的思路
     *             行的军人数量 * 100 + 当前行索引
     * @param mat
     * @param k
     * @return
     */
    public static int[] kWeakestRows(int[][] mat, int k) {
        int[] ans = new int[k];
        int[] temp = new int[mat.length];
        for(int i = 0; i < mat.length; i++) {
            int cur = mat[i][0];
            for(int j = 1; j < mat[i].length; j++) {
                if(mat[i][j] != 0) {
                    cur += mat[i][j];
                } else {
                    break;
                }
            }
            cur = cur * 100 + i;
            temp[i] = cur;
        }
        Arrays.sort(temp);
        for(int i = 0; i < k; i++) {
            ans[i] = temp[i] % 100;
        }
        return ans;
    }

    /**
     * 从列入手，遇到0说明当前行为最弱k行中一个
     * @param mat
     * @param k
     * @return
     */
    public static int[] kWeakestRows2(int[][] mat,int k) {
        int[] ans = new int[k];
        // 此时我们需要按照顺序记录在ans中，所以我们采用的是链表hashmap，而不是普通的hashmap(无序的)
        Map<Integer,Integer> map = new LinkedHashMap<>(); // key:行索引 value:行索引
        int row = mat.length; int col = mat[0].length;
        for(int j = 0; j < col; j++) { // 扫描列
            for(int i = 0; i < row; i++) { // 扫描行
                if(mat[i][j] == 0) {
                    // 判断当前map的长度
                    if(map.size() == k) {break;} // 退出循环
                    // 判断当前行是否存在
                    if(!map.containsKey(i)) {map.put(i,i);}
                }
            }
        }
        // 上述可能会出现这样一种情况：所有的列遍历完之后map中的键值对不满k个
        // 此时我们还需要添加额外的键值对到map中
        if(map.size() < k) {
            int index = 0;
            while(map.size() < k) {
                if(!map.containsKey(index)) {
                    map.put(index,index);
                }
            }
        }
        int i = 0;
        for(int key : map.keySet()) {
            ans[i] = key;
            i++;
        }
        return ans;
    }


    public static int[] kWeakestRows3(int[][] mat,int k) {
        int[][] tmp = new int[mat.length][2]; // tmp[i][0]:第i行的军人数   tmp[i][0]:第i行索引
        for (int i = 0; i < mat.length; i++) {
            tmp[i][0] = i;
            for (int j = 0; j < mat[0].length; j++) {
                if (mat[i][j] == 1) {
                    tmp[i][1] += 1;
                } else {
                    break;
                }
            }
        }
        int[] ans = new int[k];
        // 拉姆达表达式(绝了！！！)
        Arrays.sort(tmp, (o1, o2) -> o1[1] - o2[1]);
        for(int i = 0; i < k; i++) {
            ans[i] = tmp[i][0];
        }
        return ans;
    }


}
